#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

bool increment(string &str_num) {
  bool takeover = 0;
  for (auto i = str_num.size() - 1; i >= 0; --i) {
    str_num[i] = str_num[i] + takeover;
    if (i == str_num.size() - 1) {
      ++str_num[i];
    }
    if (str_num[i] > '9') {
      if (i == 0) return false;
      str_num[i] = '0';
      takeover = 1;
    } else {
      return true;
    }
  }
  return false;
}

void print(const string &str_num) {
  bool prefix0 = true;
  for (auto i = 0; i < str_num.size(); ++i) {
    if (prefix0 && str_num[i] != '0')
      prefix0 = false;
    if (!prefix0)
      cout << str_num[i];
  }
  cout << '\t';
}

void print1ToMaxNDigit(int n) {
  if (n <= 0) {
    cout << "Invalid input" << endl;
    return;
  }
  string str_num(n, '0');
  while (increment(str_num)) {
    print(str_num);
  }
}

void recursiveCore(string &str_num, int idx) {
  if (idx == str_num.size()) {
    print(str_num);
    return;
  }
  for (char i = '0'; i <= '9'; ++i) {
    str_num[idx] = i;
    recursiveCore(str_num, idx + 1);
  }
}

void print1ToMaxNDigitRecursive(int n) {
  if (n <= 0) {
    cout << "Invalid input" << endl;
    return;
  }
  string str_num(n, '0');
  recursiveCore(str_num, 0);
}

string addTwoNumPositive(const string &input1, const string &input2, int sign2) {
  string ret;
  int length1 = input1.size();
  int length2 = input2.size();
  int takeover = 0;
  for (auto idx1 = length1 - 1, idx2 = length2 - 1;
       (idx1 >= 0 || idx2 >= 0);
       --idx1, --idx2) {
    char in1 = (idx1 >= 0) ? input1[idx1] : '0';
    char in2 = (idx2 >= 0) ? input2[idx2] : '0';
    int tmp = (in1 - '0') + (in2 - '0') * sign2 + takeover;
    if (tmp > 9) {
      takeover = 1;
      tmp -= 10;
    } else if (tmp < 0) {
      takeover = -1;
      tmp += 10;
    } else {
      takeover = 0;
    }
    // ret.push_back(tmp + '0');
    ret = (char)(tmp + '0') + ret;
  }
  // reverse(ret.begin(), ret.end());
  return ret;
}

string addTwoNum(string input1, string input2) {
  string ret;
  int sign1 = input1[0] == '-' ? -1 : 1;
  int sign2 = input2[0] == '-' ? -1 : 1;
  int length1 = input1.size();
  int length2 = input2.size();
  if (sign1 == -1) {
    input1 = input1.substr(1);
    --length1;
  }
  if (sign2 == -1) {
    input2 = input2.substr(1);
    --length2;
  }
  bool has_swap = 0;
  if (length2 > length1) {
    swap(input1, input2);
    has_swap = 1;
  } else {
    for (auto i = 0; i < length1; ++i) {
      if (input1[i] != input2[i]) {
        if (input1[i] < input2[i]) {
          swap(input1, input2);
          has_swap = 1;
          break;
        } else {
          break;
        }
      }
    }
  }
  if (sign1 * sign2 == 1) {
    ret = addTwoNumPositive(input1, input2, 1);
    if (sign1 == -1) {
      ret = '-' + ret;
    }
  } else {
    ret = addTwoNumPositive(input1, input2, -1);
    if ((!has_swap && sign1 == -1) || (has_swap && sign2 == -1)) {
      ret = '-' + ret;
    }
  }
  return ret;
}

int main() {
  cout << "Iteration..." << endl;
  print1ToMaxNDigit(2);
  cout << "\nRecursive..." << endl;
  print1ToMaxNDigitRecursive(2);
  cout << "\nAdd two num in string" << endl;
  cout << "234 + 567 = " << addTwoNum("234", "567") << endl;
  cout << "-234 + 567 = " << addTwoNum("-234", "567") << endl;
  cout << "234 + (-567) = " << addTwoNum("234", "-567") << endl;
  cout << "567 + (-234) = " << addTwoNum("567", "-234") << endl;
  cout << "(-567) + 234 = " << addTwoNum("-567", "234") << endl;
  cout << "(-567) + (-234) = " << addTwoNum("-567", "-234") << endl;
  return 0;
}
